//
// Description: 91. 解码方法
// Created by Loading on 2022/6/14.
//

#include <bits/stdc++.h>

using namespace std;

int numDecodings(string s) {
    if (s[0] == '0') {
        return 0;
    }
    int n = s.size();

    // dp[i] 表示前 i 个字符的组合数
    int dp[n + 1];
    // 初始化
    memset(dp, 0, sizeof dp);
    dp[0] = dp[1] = 1;

    for (int i = 2; i <= n; ++i) {
        if (s[i - 1] == '0') {
            // 如果当前字符是 0，则必须有 10 或 20 组合，否则直接返回 0
            if (s[i - 2] != '1' && s[i - 2] != '2') {
                return 0;
            }
            // 只能由两个字符解码，故由 dp[i - 2] 转移，此时 dp[i - 1] 不合法
            dp[i] = dp[i - 2];
        } else {
            // 由当前一个字符解码
            dp[i] = dp[i - 1];
            int tmp = stoi(s.substr(i - 2, 2));
            if (tmp >= 10 && tmp <= 26) {
                // 与上一个字符合并解码，只有和这个字符能够组成 10~26 之间的数，才合法
                dp[i] += dp[i - 2];
            }
        }
    }

    return dp[n];
}

int main() {
    string s = "124156237420";

    auto res = numDecodings(s);

    cout << res << endl;

    return 0;
}